1. Field of Use
The present improvement relates to apparatus for maintaining information signifying the order of use of a plurality of units.
2. Prior art
In data processing systems having a plurality of units which are used in random sequence, there is a need to share the use of the various units; and to achieve an optimum level of performance, there is a further need to assign for each new use a unit which is least likely to require further utilization by the use currently assigned to the unit.
The preferred embodiment of the present improvement is incorporated in a cache storage system having high speed buffer storage (cache), a directory-look-aside-table (DLAT), and least recently used (LRU) or at least quasi LRU apparatus for maintaining binary coded information related to the sequence use of various sections of the buffer storage.
The cache and its DLAT are divided into a plurality of congruence classes and each congruence class includes a plurality of associativity classes. The LRU comprises a storage array having one position for each congruence class and storing therein the usage data (LRU binary code) of the associativity classes of the respective congruence class. A description of such cache storage systems is found in many patents and publications, for example, U.S. Pat. No. 3,588,829, entitled, "Integrated Memory System With Block Transfer To A Buffer Store", issued to Boland, et al on June 28, 1971 and assigned to the assignee of the present invention.
During the operation of known cache systems of this type, the LRU binary code for each congruence class is updated with each successful access to (use of) a cache storage area corresponding to one of the associativity classes of the congruence class of interest. Depending upon which associativity class is selected for access, certain LRU bits of the binary code must be updated. Remaining bits of the binary code do not require updating because they maintain the history of previous accesses and do not change.
In addition, the LRU storage array includes in each congruence class position one "modify" bit for each associativity class. Each of these bits is set to "0", when new data is entered into the cache area corresponding to the associativity class.
The modify bit is changed to a "1" only if this new data is modified, for example by a CPU write to cache. Hence, these modify bits must be updated during system operation.
Because not all LRU bits in an LRU binary code are updated during successful accesses to the cache, known systems have typically read out, from the appropriate LRU array position, all of the binary code bits, both those requiring update and those that do not. The former bits are updated and all bits, updated and non-updated, are returned to the array position. This is referred to in the prior art as a READ/MODIFY/WRITE (RMW) cycle for update operations.
It is necessary for system performance to successfully perform the RMW cycle during a CPU system cycle. As system speeds increase, the RMW cycle places limitations on system cycle times.
It is, therefore a primary object of the present improvement to minimize the time required for updating usage data and/or modify bits.
It is a more specific object of the present improvement to perform LRU and/or modify bit updating without the need for a RMW cycle of operation.